// 使用动态规划实现凑零钱
// ref: 力扣322题 零钱兑换 https://leetcode.cn/problems/coin-change/description

#include <vector>
#include <iostream>
#include <limits.h>

#define INVALID -888

/**
 *! @brief 使用动态规划实现凑零钱问题(自上而下递归)
 * 
 * @param  coins   可选的硬币面值
 * @param  amount  需要凑成钱的总金额
 * 
 * @return int     最少需要的硬币枚数
 */
int coinChangeV1(const std::vector<int> &coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0)  return -1;

    int res = INT32_MAX;          //! 浮点数: FLT_MAX, DBL_MAX
    for(const auto& coin : coins) {
        int subRes = coinChangeV1(coins, amount - coin);
        if (subRes == -1) continue;
        res = std::min(res, subRes + 1);
    }
    FLT_MAX
    return res == INT32_MAX? -1 : res;
}




/**
 *! @brief 使用动态规划实现凑零钱问题(自上而下递归, 使用备忘录优化)
 * 
 * @param  coins   可选的硬币面值
 * @param  memo    备忘录
 * @param  amount  需要凑成钱的总金额
 * 
 * @return int     最少需要的硬币枚数
 */
int coinChangeV2(const std::vector<int> &coins, std::vector<int>& memo, int amount) {
    if (amount == 0) return 0;
    if (amount < 0)  return -1;

    int res = INT32_MAX;
    for(const auto& coin : coins) {
        int subRes = INVALID;
        if (memo[amount - coin] != INVALID){
            subRes = memo[amount - coin];
        } else {
            subRes = coinChangeV2(coins, memo, amount - coin);
        }
        if (subRes == -1) continue;

        memo[amount] = subRes + 1;
        res = std::min(res, subRes + 1);
    }
    return res == INT32_MAX? -1 : res;
}




/**
 *! @brief 使用动态规划实现凑零钱问题(自下而上递推)
 * 
 * @param  coins   可选的硬币面值
 * @param  amount  需要凑成钱的总金额
 * 
 * @return int     最少需要的硬币枚数 
 */
int coinChangeV3(const std::vector<int> &coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0)  return -1;
    std::vector<int> memo(amount + 1, 0); 

    for (size_t i = 1; i <= amount; i++) {
        int res = INT32_MAX;
        for (const auto& coin : coins) {
            if (i - coin < 0) continue;
            res = std::min(res, memo[i - coin] + 1);
        }
        memo[i] = res == INT32_MAX? -1 : res;
    }

    return memo[amount];
}




int main(int argc, char const *argv[]) {
    int amount = 130;
    std::vector<int> coins = {1, 2, 5};
    std::vector<int> memo(amount + 1, INVALID);

    // int res    = coinChangeV1(coins, amount);        // amount > 35+ 就明显看出来很慢了
    // int res    = coinChangeV2(coins, memo, amount);
    // int res    = coinChangeV3(coins, amount); 
    std::cout << res << std::endl;

    return 0;
}